// https://leetcode.cn/problems/construct-string-from-binary-tree/
// Created by ade on 2022/8/10.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    string tree2str(TreeNode *node) {
        if (!node) return "";
        string tmp = to_string(node->val);
        if (!node->left && !node->right) {
            return tmp;

        }
        if (!node->right) {
            return tmp + "(" + tree2str(node->left) + ")";
        }
        return tmp + "(" + tree2str(node->left) + ")(" + tree2str(node->right) + ")";
    }


    TreeNode *init() {
        TreeNode *h1 = new TreeNode(1);
        TreeNode *h2 = new TreeNode(2);
        TreeNode *h3 = new TreeNode(3);
        TreeNode *h4 = new TreeNode(4);
        h1->left = h2;
        h2->left = h4;
        h1->right = h3;
        return h1;
    }
};

int main() {
    Solution so;
    TreeNode *h1 = so.init();
    auto res = so.tree2str(h1);
    cout << res << endl;
    return 0;
}